#define _CRT_SECURE_NO_WANINGS 1
#pragma warning(disable: 4996)

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int StackDatatype;
typedef struct Stack
{
    StackDatatype* data;
    int capacity;
    int Top;
}ST;
void StackInit(ST* pst)
{
    assert(pst);
    pst->capacity = 0;
    pst->data = NULL;
    pst->Top = -1;
}
void JudgeCapacity(ST* pst)
{
    assert(pst);
    if (pst->capacity == pst->Top)
    {
        int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
        StackDatatype* tmp = (StackDatatype*)realloc(pst->data, sizeof(StackDatatype) * newcapacity);
        if (tmp == NULL)
        {
            perror("malloc failed!");
            return;
        }
        pst->data = tmp;
        pst->capacity = newcapacity;
    }

}

void Push(ST* pst, StackDatatype x)
{
    assert(pst);
    pst->Top++;
    JudgeCapacity(pst);

    pst->data[pst->Top] = x;
}
void Pop(ST* pst)
{
    assert(pst);
    assert(pst->Top > -1);
    pst->Top--;
}
StackDatatype StackTop(ST* pst)
{
    assert(pst);
    return pst->data[pst->Top];
}
int StackSize(ST* pst)
{
    assert(pst);
    return pst->Top + 1;
}
bool StackEmpty(ST* pst)
{
    assert(pst);
    return pst->Top == -1;
}
void StackDestroy(ST* pst)
{
    assert(pst);
    free(pst->data);
    pst->data = NULL;
    pst->capacity = pst->Top = 0;
}


typedef struct {
    ST s1;
    ST s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&mq->s1);
    StackInit(&mq->s2);
    return mq;
}

void myQueuePush(MyQueue* obj, int x) {
    if (StackEmpty(&obj->s1))
    {
        Push(&obj->s2, x);
    }
    else
    {
        Push(&obj->s1, x);
    }
}

int myQueuePop(MyQueue* obj) {
    if (StackEmpty(&obj->s1))
    {

        while (!StackEmpty(&obj->s2))
        {
            Push(&obj->s1, StackTop(&obj->s2));
            Pop(&obj->s2);
        }
        int pop = StackTop(&obj->s1);
        Pop(&obj->s1);
        while (!StackEmpty(&obj->s1))
        {
            Push(&obj->s2, StackTop(&obj->s1));
            Pop(&obj->s1);
        }

        if (!StackEmpty(&obj->s1))
        {
            Pop(&obj->s1);
        }
        return pop;
    }
    else
    {

        while (!StackEmpty(&obj->s1))
        {
            Push(&obj->s2, StackTop(&obj->s1));
            Pop(&obj->s1);
        }
        int pop = StackTop(&obj->s2);
        while (!StackEmpty(&obj->s2))
        {
            Push(&obj->s1, StackTop(&obj->s2));
            Pop(&obj->s2);
        }

        if (!StackEmpty(&obj->s2))
        {
            Pop(&obj->s2);
        }
        return pop;
    }

}


int myQueuePeek(MyQueue* obj) {
    ST unemptySt = obj->s1;
    ST emptySt = obj->s2;
    if (StackEmpty(&obj->s1))
    {
        unemptySt = obj->s2;
        emptySt = obj->s1;
    }
    while (!StackEmpty(&unemptySt))
    {
        Push(&emptySt, StackTop(&unemptySt));
        Pop(&unemptySt);
    }
    int peek = StackTop(&emptySt);
    while (!StackEmpty(&emptySt))
    {
        Push(&unemptySt, StackTop(&emptySt));
        Pop(&emptySt);
    }
    return peek;

}

bool myQueueEmpty(MyQueue* obj) {
    return (StackEmpty(&obj->s1) && StackEmpty(&obj->s2));
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
    obj = NULL;
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/